package com.tgy.algorithm.base._滑动窗口;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 假设一个固定大小为W的窗口，返回每一次滑出状况的最大值例如，
 * arr =[4,3,5,4,3,3,6,7],W=3
 * [5,5,5,4,6,7]返回:
 */
public class _每次滑动窗口的最大值 {

    public static int[] getEachWindowMax(int[] nums,int w) {

        if (w <= 0) {
            return new int[]{};
        }

        // 8 - 3 + 1
        int len = nums.length;
        if (w >= len) {

            int max = Integer.MIN_VALUE;
            for (int i = 0; i < len; i++) {
                max = Math.max(max,nums[i]);
            }

            return new int[]{max};
        }
        int[] maxs = new int[len - w + 1];
        LinkedList<Integer> queue = new LinkedList<>();

        for (int i = 0; i < len; i++) {
            int val = nums[i];
            while (!queue.isEmpty() && nums[queue.peekLast()] <= val) {
                queue.pollLast();
            }

            queue.offerLast(i);
            int lw =  i - w;
            if (queue.peekFirst() == lw) {
                queue.pollFirst();
            }
            if (lw + 1 >= 0) {
                maxs[lw+1] = nums[queue.peekFirst()];
            }
        }

        return maxs;
    }

    public static void test01() {
        LinkedList<Integer> queue = new LinkedList<>();

        queue.offerFirst(1);
        queue.offerFirst(2);
        queue.offerLast(3);
        queue.offerLast(4);
        System.out.println(queue);

        while (!queue.isEmpty()) {
            System.out.println(queue.pollFirst());
        }
    }

    public static void main(String[] args) {
        int[] nums = {4,3,5,4,3,3,6,7};
        int[] eachWindowMax = getEachWindowMax(nums, 3);
        System.out.println(Arrays.toString(eachWindowMax));
    }
}
